#include <iostream>
#include <vector>
using namespace std;

int maximalRectangle(vector<vector<char> > &matrix) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function

    if(matrix.size() == 0)
        return 0;
    int width = matrix[0].size();
    int height = matrix.size();
    int *leftMax = new int[width * height];
    for(int i=0; i<width * height; ++i){
        leftMax[i] = 0;
    }
    int maxArea = 0;
    for(int i=0; i<matrix.size(); ++i)
        for(int j=0; j<matrix[i].size(); ++j){
            if(matrix[i][j] == '0'){
                leftMax[width*i + j] = 0;
            }
            else{
                leftMax[width*i + j] = 1;
                if(j>0){
                    leftMax[width*i + j] += leftMax[width*i + j - 1];
                }

                int curWidth = leftMax[width*i + j];
                int curI = i;
                while(curI>0 && matrix[i][j] != '0'){
                    curWidth = curWidth > leftMax[width * curI + j] ? leftMax[width * curI + j] : curWidth;
                    int curArea = (i - curI + 1) * curWidth;
                    if(curArea > maxArea)
                        maxArea = curArea;
                    --curI;
                }
            }
        }
    delete []leftMax;
    return maxArea;
}

int main(){
    return 0;
}